import { ListNode } from '../../helper/ListNode'
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * 栈方法
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
export var removeNthFromEnd = function (head, n) {
  let dummy = new ListNode(-1, head)
  const stack = []
  let cur = dummy
  while (cur) {
    stack.push(cur)
    cur = cur.next
  }
  for (let i = 0; i < n; i++) {
    stack.pop()
  }
  const prev = stack[stack.length - 1]
  prev.next = prev.next.next
  return dummy.next
}

/**
 * 双指针
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
export var removeNthFromEnd2 = function (head, n) {
  const dummy = new ListNode(-1, head)
  let fast = dummy
  let slow = dummy
  // 快指针先走 n 步
  for (let i = 0; i < n; i++) {
    fast = fast.next
  }
  // 快慢指针同时走，
  // 最后快指针到达尾部时，慢指针指向的就是倒数第 n + 1 个节点, 即删除节点的前一个节点
  while (fast.next) {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return dummy.next
}
